package com.hardy.leetcode;

/**
 * Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed? Would this affect
 * the run-time complexity? How and why? Write a function to determine if a given target is in the
 * array. User: Ruijie Date: 2016/9/19
 */
public class SearchInRotatedSortedArrayLi {

    public static boolean search(int[] A, int target) {
        int left = 0;
        int right = A.length - 1;
        int middle = left;
        while(left<=right){
            middle=left+(right-left)/2;
            if(A[middle]==target){
                return true;
            }
            if(A[left]>A[middle]){
                if(A[middle]<target&&target<=A[right]){
                    left=middle+1;
                }else{
                    right=middle-1;
                }
            }else if(A[left]<A[middle]){
                if(A[left]<=target&&target<A[middle]){
                    right=middle-1;
                }else{
                    left=middle+1;
                }
            }else{
                left++;
            }
        }
        return false;
    }


    public static void main(String[] args) {
        int[] array={5,6,7,8,1,2,3,4};
        System.out.println(search(array,5));
        System.out.println(search(array,6));
        System.out.println(search(array,7));
        System.out.println(search(array,8));
        System.out.println(search(array,1));
        System.out.println(search(array,2));
        System.out.println(search(array,3));
        System.out.println(search(array,4));

    }
}
